๐Ÿ‘ฉโ€๐Ÿ’ป 60059. ์ž๋ฌผ์‡ ์™€ ์—ด์‡ 

@Seongukbaek Posted June 12, 2022 ยท Updated June 12, 2022 ยท 4 min read

๋ฌธ์ œ

Programmers - ์ž๋ฌผ์‡ ์™€ ์—ด์‡ 

๐Ÿ“ Logic

for (int r = 0; r < M - 1 + N; r++) { for (int c = 0; c < M - 1 + N; c++) { for (int rotate = 0; rotate < 4; rotate++) { // ์ž๋ฌผ์‡ ๋ฅผ ์ค‘์•™์— ๋‘๊ณ , ํ‚ค๋ฅผ ๋Œ๋ ค๊ฐ€๋ฉด์„œ ํ™•์ธํ•  ํฐ ๋ฐฐ์—ด ์„ ์–ธ bigMap = new int[N + (M - 1) * 2][N + (M - 1) * 2]; // ์ž๋ฌผ์‡ ๋ฅผ ์ค‘์•™์— ๋ฐฐ์น˜ for (int i = 0; i < N; i++) System.arraycopy(lock[i], 0, bigMap[M - 1 + i], M - 1, N); // bigMap์— ํ‚ค๋ฅผ ๋”ํ•ด ์ž๋ฌผ์‡ ์— ๋งž๋Š”์ง€ ํ™•์ธํ•  ๊ฒƒ match(key, r, c); if (canUnlock()) return true; } } }
  • ์ „์ฒด ํ๋ฆ„์€,

    • ์ž๋ฌผ์‡ ์™€ ํ‚ค๋ฅผ ๋‘˜ ์ˆ˜ ์žˆ๋Š” ํฐ 2์ฐจ์› ๋ฐฐ์—ด์„ ์„ ์–ธํ•˜๊ณ ,
    • ์ž๋ฌผ์‡ ๋ฅผ ์ค‘์•™์— ๋‘” ์ฑ„๋กœ, ํ‚ค๋ฅผ ๋Œ๋ ค๊ฐ€๋ฉด์„œ ๋งž์ถฐ๋ณด๊ณ , ์ž ๊ธˆ ํ•ด์ œ๊ฐ€ ๊ฐ€๋Šฅํ•œ์ง€ ํ™•์ธํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Solution { static int M; static int N; static int[][] bigMap; public boolean solution(int[][] key, int[][] lock) { M = key.length; N = lock.length; for (int r = 0; r < M - 1 + N; r++) { for (int c = 0; c < M - 1 + N; c++) { for (int rotate = 0; rotate < 4; rotate++) { // ์ž๋ฌผ์‡ ๋ฅผ ์ค‘์•™์— ๋‘๊ณ , ํ‚ค๋ฅผ ๋Œ๋ ค๊ฐ€๋ฉด์„œ ํ™•์ธํ•  ํฐ ๋ฐฐ์—ด ์„ ์–ธ bigMap = new int[N + (M - 1) * 2][N + (M - 1) * 2]; // ์ž๋ฌผ์‡ ๋ฅผ ์ค‘์•™์— ๋ฐฐ์น˜ for (int i = 0; i < N; i++) System.arraycopy(lock[i], 0, bigMap[M - 1 + i], M - 1, N); // bigMap์— ํ‚ค๋ฅผ ๋”ํ•ด ์ž๋ฌผ์‡ ์— ๋งž๋Š”์ง€ ํ™•์ธํ•  ๊ฒƒ match(key, r, c); if (canUnlock()) return true; } } } return false; } // bigMap์ด 1๋กœ๋งŒ ์ด๋ฃจ์–ด์ง€๋Š”์ง€ ํ™•์ธ static private boolean canUnlock() { for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (bigMap[M - 1 + i][M - 1 + j] != 1) return false; return true; } // ํ‚ค์™€ ์ž๋ฌผ์‡ ๋ฅผ ๋”ํ•˜๋Š” ํ•จ์ˆ˜ static private void match(int[][] key, int r, int c) { key = rotatingKey(key); for (int i = 0; i < M; i++) for (int j = 0; j < M; j++) bigMap[i + r][j + c] += key[i][j]; } // ํ‚ค๋ฅผ ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ 90๋„ ๋Œ๋ฆฌ๋Š” ํ•จ์ˆ˜ static private int[][] rotatingKey(int[][] key) { for (int i = 0; i < M / 2; i++) { int[] tmp = Arrays.copyOf(key[M - i - 1], M); key[M - i - 1] = key[i]; key[i] = tmp; } for (int i = 0; i < M; i++) { for (int j = i; j < M; j++) { int temp = key[i][j]; key[i][j] = key[j][i]; key[j][i] = temp; } } return key; } }

โœ๏ธ Review

  • ์ด๋ฒˆ ์ฃผ์ฐจ ๋ฌธ์ œ ์ค‘์—์„œ ์ œ์ผ ์–ด๋ ค์› ๋˜ ๋ฌธ์ œ
  • ๊ตฌํ˜„์ด ๊น”๋”ํ•˜๊ฒŒ ์ด๋ค„์ง€์ง€ ์•Š์•„ ํ’€์ด ์˜์ƒ์„ ๋ณด๋‹ˆ, ์•„๋ž˜์™€ ๊ฐ™์€ ์‹ ๊ธฐํ•œ ํ’€์ด๋ฅผ ๋ณผ ์ˆ˜ ์žˆ์—ˆ๋‹ค.

    • ํ‚ค๋ฅผ ๋Œ๋ฆฌ์ง€ ์•Š๊ณ  ์ธ๋ฑ์Šค ์ ‘๊ทผ์œผ๋กœ ๊ตฌํ˜„
    • ์ž๋ฌผ์‡ ๋ฅผ ์ค‘์•™์— ๋‘๊ณ , ํ‚ค๋ฅผ ์—ฌ๋Ÿฌ ๋ฐฉ๋ฉด์—์„œ ๋”ํ•ด๋ณผ ์ˆ˜ ์žˆ๋Š” ํฐ ๋ฐฐ์—ด ์„ ์–ธ
  • ์ด๋Ÿฐ ๊ตฌํ˜„ ๋ฌธ์ œ๋Š” ๋จธ๋ฆฌ๋ฅผ ์ข€ ์ž˜ ๊ตด๋ฆด ์ค„ ์•Œ์•„์•ผ ํ•  ๊ฒƒ ๊ฐ™๋‹ค...
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€